package LeetCode;

import java.util.ArrayList;

public class LetterCombforPhone {
  public static char c[][] = { { ' ' }, { ' ' }, { 'a', 'b', 'c' },
      { 'd', 'e', 'f' }, { 'g', 'h', 'i' }, { 'j', 'k', 'l' },
      { 'm', 'n', 'o' }, { 'p', 'q', 'r', 's' }, { 't', 'u', 'v' },
      { 'w', 'x', 'y', 'z' } };

  //pass both
  public static ArrayList<String> letterCombinations(String digits) {
    ArrayList<String> result = new ArrayList<String>();

    int n = digits.length();
    int answer[] = new int[n];
    while (true) {
      String comb = "";
      for (int i = 0; i < n; i++)
        comb += c[digits.charAt(i) - '0'][answer[i]];
      result.add(comb);

      int k = n - 1;
      while (k >= 0) {
        if (answer[k] < c[digits.charAt(k) - '0'].length - 1) {
          answer[k]++;
          break;
        } else {
          answer[k] = 0;
          k--;
        }
      }
      if (k < 0)
        break;

    }
    return result;
  }

  /**
   * @param args
   */
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    System.out.println(letterCombinations("312").toString());
  }

}
